数据结构 (Data Structures)

常用数据结构的 JavaScript 实现。

1. 栈 (Stack)

后进先出 (LIFO)。

class Stack {
  constructor() {
    this.items = [];
  }

  // 入栈
  push(element) {
    this.items.push(element);
  }

  // 出栈
  pop() {
    return this.items.pop();
  }

  // 查看栈顶
  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

2. 队列 (Queue)

先进先出 (FIFO)。

class Queue {
  constructor() {
    this.items = [];
  }

  // 入队
  enqueue(element) {
    this.items.push(element);
  }

  // 出队
  dequeue() {
    return this.items.shift();
  }

  // 查看队首
  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

3. 链表 (LinkedList)

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  push(element) {
    const node = new Node(element);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.count++;
  }
  
  // 更多方法如 insert, removeAt, indexOf 略...
}

4. 二叉搜索树 (BST)

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(key) {
    if (!this.root) this.root = new Node(key);
    else this.insertNode(this.root, key);
  }

  insertNode(node, key) {
    if (key < node.key) {
      if (!node.left) node.left = new Node(key);
      else this.insertNode(node.left, key);
    } else {
      if (!node.right) node.right = new Node(key);
      else this.insertNode(node.right, key);
    }
  }
  
  // 遍历方法 (inOrder, preOrder, postOrder) 略...
}